package cn.wgx.study.algorithm;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort extends SortBase {


    public static int[] sort(int array[]) {
        int tmp[] = new int[array.length];
        int i = 0, j = array.length / 2;
        fill(array, tmp, 0, i, j, array.length);
        return tmp;
    }

    private static void fill(int[] a, int[] tmp, int k, int i, int j, int len) {
        tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
        if (j >= len) {
            while (k < len) {
                tmp[k++] = a[i++];
            }
        } else if (i >= len / 2) {
            while (k < len) {
                tmp[k++] = a[j++];
            }
        } else {
            fill(a, tmp, k, i, j, len);
        }
    }


    public static void main(String[] args) {
//        int[] array = generate(100, 100);
//        int[] array = {99, 45, 75, 84, 24, 72, 69, 51, 90, 93, 97, 19, 99, 36, 10, 12, 54, 37, 44, 14, 60, 29, 77, 60, 81, 65, 65, 49, 53, 71, 40, 20, 27, 90, 12, 43, 49, 17, 70, 80, 68, 21, 61, 19, 47, 28, 90, 38, 94, 81, 75, 6, 0, 64, 63, 64, 94, 38, 13, 62, 5, 67, 73, 36, 0, 22, 67, 82, 70, 8, 66, 43, 30, 11, 25, 60, 88, 69, 18, 80, 93, 76, 69, 5, 56, 10, 96, 4, 83, 67, 99, 9, 9, 63, 69, 10, 17, 6, 99, 89};
        int[] array = {5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6,66};
        int[] array1 = Arrays.copyOf(array, array.length);
        int[] array2 = Arrays.copyOf(array, array.length);
        print(array);

        array1 = sort(array1);
        Arrays.sort(array2);

        print(array1);
        print(array2);
        System.out.println(compare(array1, array2));
    }
}
